import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.Collections;
import java.util.Random;
import java.util.Vector;


public class Graph {
	private Vertex vertices[];
	private Vector<Edge> edges = new Vector<Edge>();
	private int numVertices; 
	private double maxEdge;
	private double maxEdgeCost;
	private Random generator = new Random();
		
	Graph(String[] args) throws IOException {
		try {
			BufferedReader in = new BufferedReader(new FileReader(args[0]));
			String nextLine;
			String words[];
			double weight;
			
			while ((nextLine = in.readLine()) != null) {
				if (nextLine.startsWith("#")) {
					words = (nextLine.trim()).split(" ");
					
					numVertices = Integer.parseInt(words[1]);
					setVertices();
				}
				
				else {
					words = (nextLine.trim()).split("\t");
					weight = Double.parseDouble(words[2]);
					if (maxEdge < weight)
						maxEdge = weight;
					
					edges.add(new Edge(vertices[Integer.parseInt(words[0])], vertices[Integer.parseInt(words[1])], 
							  weight));
				}
			}
			
			in.close();
		} catch (FileNotFoundException e) {
		} 
		
		sortVertEdges();

		maxEdgeCost = 10*maxEdge;

	}
	
	private void setVertices() {
		vertices = new Vertex[numVertices+1];
		for (int i = 0; i < vertices.length; i++) {
			vertices[i] = new Vertex(i);
		}
	}
	
	private void sortVertEdges() {
		for (int i = 1; i < vertices.length; i++) {
			vertices[i].sort();
		}
	}
	
	public void print() {
		System.out.println("# " + numVertices);
		
		for (int i = 0; i < edges.size(); i++) {
			edges.get(i).print();
		}
	}
	
	public boolean hasVertex(int i) {
		if (vertices[i] != null) {
			return true;
		}
		
		else 
			return false;
	}
	
	Edge findNearest(Vertex vert) {
		Edge ret;
		
		for (int i = 1; i < vertices.length; i++) {
			if (!vertices[i].visited) {
				ret = new Edge(vert, vertices[i], maxEdgeCost); 
				//System.out.println("Nearest edge: " + ret.getV1().getIndex() + " " + ret.getV2().getIndex() + " " + ret.getWeight());
				return ret;
			}
		}
		
		return null;
	}
	
	private void resetVisited() {
		for (int i = 1; i < vertices.length; i++) {
			vertices[i].visited = false;
		}
	}
	
	public Tour findBestGreedy() {
		int index = 0;
		Tour tOld, tNew;
		
		//if (vertices.length < 1000) {
			tOld = greedy(1);
		
			for (int i = 2; i < vertices.length; i++) {
				resetVisited();
				tNew = greedy(i);

				if (tOld.length > tNew.length) {
					tOld = tNew;
				}
			}
			return tOld;
		//}
		
		/*else {
			int i = 2;
			int r;
			
			tOld = greedy(1);

			while (i < 2500) {
				r = generator.nextInt(vertices.length);
				if (r == 0) 
					r++;
				
				resetVisited();
				tNew = greedy(r);
				if (tOld.length > tNew.length) {
					tOld = tNew;
				}
				
				i++;
			}
			return tOld;
		}*/
	}
	public Tour greedy(int i) {
		double cost = 0;
		Tour t = new Tour();

		Vertex root = vertices[i];
		Vertex current = root;

		Vertex next;
		
		Edge edge_next;
		
		while(true) {
			current.visited = true;
			t.sTour.add("" + current.getIndex());
			edge_next = current.greedyNext(); 
			
			if (edge_next == null) {
				edge_next = findNearest(current);
				
				if(edge_next == null) {
					int index = current.connectedTo(root);
					
					if (index >= 0) {
						t.tour.add(current.edges[index]);
						cost += current.edges[index].getWeight();
					}
					
					else {
						t.tour.add(new Edge(current,root,maxEdgeCost));
						cost += maxEdgeCost;
					}
					
					t.length = cost;
					t.sTour.add("-1");
					return t;
				}
			}
			
			t.tour.add(edge_next);
			
			//get weight to increase cost of traversal
			cost += edge_next.getWeight();
			
			//get the next vertex from the edge
			next = edge_next.getV2();
				
			//move to the next vertex
			current = next;
		}
		
	}
	
	private Tour twoOptMove(Tour oldTour) {
		Edge temp1, temp2;
		int index;
		
		//make a deep copy
		Tour mTour = new Tour(oldTour);
		
		//remove random edge 
		int rand = generator.nextInt(mTour.tour.size());
		temp1 = mTour.tour.remove(rand);
		mTour.length -= temp1.getWeight();
		
		//remove second random edge
		rand = generator.nextInt(mTour.tour.size());
		temp2 = mTour.tour.remove(rand);
		mTour.length -= temp2.getWeight();
		
		//temp 1 vertex 1
		Vertex t1v1 = temp1.getV1();
		Vertex t1v2 = temp1.getV2();
		Vertex t2v1 = temp2.getV1();
		Vertex t2v2 = temp2.getV2();
		
		//Reconnect edges
		index = t1v1.connectedTo(t2v2);
		if (index >= 0) {
			mTour.tour.add(t1v1.edges[index]);
			mTour.length += t1v1.edges[index].getWeight();
		}
		
		else {
			mTour.tour.add(new Edge(t1v1, t2v2,maxEdgeCost));
			mTour.length += maxEdgeCost;
		}
		
		index = t1v2.connectedTo(t2v1);
		if (index >= 0) {
			mTour.tour.add(t1v2.edges[index]);
			mTour.length += t1v2.edges[index].getWeight();
		}
		
		else {
			mTour.tour.add(new Edge(t1v2, t2v1, maxEdgeCost));
			mTour.length += maxEdgeCost;
		}
		
		return mTour;
	}
	
	public Tour twoOpt(Tour currTour) {
		Tour mTour = new Tour();

		//intial temperuture
		double temp = 2000;
		//reduce temp by 1% each iteration
		double percent = 0.99;

		
		while (temp > 0.01) {
			mTour = twoOptMove(currTour);

			if (mTour.length < currTour.length) {
				currTour = new Tour(mTour);
			}
			
			else if (generator.nextDouble() < Math.exp(currTour.length - mTour.length)/temp) {
				currTour = new Tour(mTour);
			}
			
			temp = temp*percent;
		}	
		
		return currTour;
	}
	
	
	public void checkAllVisited() {
		int count = 0;
		
		for (int i = 0; i < vertices.length; i++) {
			if (!vertices[i].visited) {
				System.out.println("Unvisited node: " + vertices[i].getIndex());
				count++;
			}
		}
		System.out.println("Number of unvisited nodes: " + count);
	}
	
	public void tsp() {
		
		Tour currTour = findBestGreedy();
		currTour.printTour();
		//System.err.println(currTour.length);
		
		//Tour modTour = twoOpt(currTour);
		//System.err.println(modTour.length);
		//modTour.fixPath();
		//modTour.printTour();

		
		//modTour.printTour();
	}
	/**
	 * @param args
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		Graph g = new Graph(args);

		g.tsp();
	}
}
